package puzzle.projecteuler.p100;

import java.util.ArrayList;
import java.util.List;

import astudy.util.AdvMath;

/**
 * 注意：这个程序搜索在10000以内唯一满足条件的5元数组。
 * 但是并不保证是和最小的一组。
 * 只不过，恰好就是答案。
 * @author Administrator
 *
 */
public class Problem060 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int max = 10000;
		Integer[] ps = AdvMath.primes(max);
		System.out.println(ps.length);
		System.out.println(find(5, ps));
	}
	
	public static boolean isFriend(int p, int q, Integer[] ps) {
		
		long m = Long.valueOf(String.valueOf(p)+String.valueOf(q));
		long n = Long.valueOf(String.valueOf(q)+String.valueOf(p));
		return minPrimeIn(m, ps) == null && minPrimeIn(n, ps) == null;
	}
	
	public static Integer minPrimeIn(long m, Integer[] ps) {
		for (Integer p : ps) {
			if (m>=p*p) {
				if (m%p == 0) {
					return p;
				}
			} else {
				break;
			}
			
		}
		return null;
	}
	
	public static List<List<Integer>> find(int n, Integer[] ps) {
		
		List<List<Integer>> as = new ArrayList<List<Integer>>();
		if (n < 2) {
		} else if (n == 2) {
			for (int i = 0; i < ps.length; i ++) {
				for (int j = i+1; j < ps.length; j ++) {
					if (isFriend(ps[i], ps[j], ps)) {
						List<Integer> a = new ArrayList<Integer>();
						a.add(ps[i]);
						a.add(ps[j]);
						as.add(a);
					}
				}
			}
		} else {
			List<List<Integer>> bs = find(n-1, ps);
			for (List<Integer> b: bs) {
				Integer last = b.get(b.size()-1);
				for (int k = 0; k < ps.length; k ++) {
					if (ps[k] > last) {
						boolean friend = true;
						for (Integer p: b) {
							if (!isFriend(p, ps[k], ps)) {
								friend = false;
								break;
							}
						}
						if (friend) {
							List<Integer> a = new ArrayList<Integer>();
							a.addAll(b);
							a.add(ps[k]);
							as.add(a);
						}
					}
				}
			}
		}
		return as;
	}
}
